2-2

\!\(\*"\""\)\!\(\*"Resistance"\)\!\(\*" "\)\!\(\*"Distance"\)\!\(\*"\""\)

Nicholas Wheeler
29 October 2011

Introduction

A web search conducted at the end of "Master Equations" (Notebook dated 26 October 2011) led me fortuitously to a site

Hyperlink["Resistance Distance","http://en.wikipedia.org/wiki/Resistance_distance"]

which reports a pretty method for computing the resistance between any two nodes of a DC circuit. The method in question is the work of D. J. Klein [Dept. of Marine Sciences, Texas A & M] and M. Randić [Dept. of Mathematics, Drake University], published as "Resistance distance," J. of Mathematical Chemistry 12, 81 - 95 (1993). In the notebook just cited I illustrate the method—a distinguishing feature of which is that it draws upon the Moore-Penrose "psuedo-inverse"—as it pertains to a cubic array of unit resistors. I suspect—and it is my objective here to demonstrate—that it pertains also to arbitrary arrays of arbitrary resistors. 

The web site makes allusion only to arrays of unit resistors, but the Klein-Randić method would be of little interest if it worked only when all resistors in an array have unit value. The method exploits many of the ideas and graph-theoretic constructs central to my (Maxwell's!) variational method (which suffers from no such limitation), but strikes me as being much more elegantly efficient than the variational method from at least a computational point of view…even though it does not (at least in its present state of development) speak as forcefully to physical intuition as does the variational method.

My plan is to assign resistances (conductances) randomly to the edges of a complete 5-node graph

and then (1) to use the variational method to evaluate a representative sample of the

4+3+2+1

possible effective resistances  (Subscript[R, i,j]) and finally (2) to compare those results with results produced by the Klein-Randić method.

Construction of the Laplacian matrix of a randomly weighted 5-node graph

We proceed

𝕒={Join[{0},Table[RandomReal[],{k,1,4}]],
Join[{0,0},Table[RandomReal[],{k,1,3}]],
Join[{0,0,0},Table[RandomReal[],{k,1,2}]],
Join[{0,0,0,0},Table[RandomReal[],{k,1,1}]],
{0,0,0,0,0}};

𝕒//MatrixForm

𝕓=𝕒+Transpose[𝕒];
𝕓//MatrixForm

𝕕=DiagonalMatrix[Table[Total[𝕓[[k]]],{k,1,5}]]
𝕕//MatrixForm

𝕃=𝕓-𝕕;
𝕃//MatrixForm

and demonstrate that the symmetric matrix 𝕃 does indeed possess the properties expected/required of a Laplacian matrix:

Table[Total[𝕃[[k]]],{k,1,5}]
Eigenvalues[𝕃]

Effective resistances by dissipation minimization

The Laplacian matrix 𝕃, as constructed above, has just been shown to be negative semi-definite, so it is the negative of the matrix we need to describe dissipation. Working therefore from

𝔻=-𝕃;

Eigenvalues[𝔻]

the dissipation rate (net (I^2)R-loss rate) is

Diss=Expand[Transpose[(({{(Subscript[V, 1])}, {(Subscript[V, 2])}, {(Subscript[V, 3])}, {(Subscript[V, 4])}, {(Subscript[V, 5])}}))].𝔻.(({{(Subscript[V, 1])}, {(Subscript[V, 2])}, {(Subscript[V, 3])}, {(Subscript[V, 4])}, {(Subscript[V, 5])}}))][[1]]

This quadratic form is to be minimized subject to constraints (Kirchhoff's nodal rule, expressed in terms of nodal potentials) that for a free circuit (one not hooked up to a current source) would read

FreeConstraints=Table[Sum[𝕃[[j]][[k]](Subscript[V, k]),{k,1,5}]==0,{j,1,5}]

but when unit current is inject at one node (node #1, let us say) and extracted at another (node #2, let us say) must be modified:

(Subscript[C, 12])=Table[Sum[𝕃[[j]][[k]](Subscript[V, k]),{k,1,5}]==KroneckerDelta[j,2]-KroneckerDelta[j,1],{j,1,5}]

The command

Minimize[Flatten[{Diss,(Subscript[C, 12])}],{(Subscript[V, 1]),(Subscript[V, 2]),(Subscript[V, 3]),(Subscript[V, 4]),(Subscript[V, 5])}]

now supplies

(Subscript[EffectiveResistance, 12])=1.13181

Notice that the interior nodal potentials {(Subscript[V, 3]),(Subscript[V, 4]),(Subscript[V, 5])} are bounded above by (Subscript[V, 1]) and below by (Subscript[V, 2]).

The Klein-Randić Method

From

Det[𝔻]

we see that 𝔻—equivalently 𝕃—is singular, so does not possess an inverse. It does, however, possess a Moore-Penrose pseudoinverse, which Mathematica knows how to construct:

?PseudoInverse

Klein & Randić claim that if we do so

Γ=PseudoInverse[𝔻]

REMARK: We note in passing that

Det[Γ]//Chop

then

(Subscript[R, effective])[i_,j_]:=Γ[[i]][[i]]+Γ[[j]][[j]]-2Γ[[i]][[j]]

which in the present instance supplies

(Subscript[R, effective])[1,2]

—in precise agreement with the result obtain above by the variational method. Similarly,

(Subscript[R, effective])[2,5]

while in that case the variational method proceeds

(Subscript[C, 25])=Table[Sum[𝕃[[j]][[k]](Subscript[V, k]),{k,1,5}]==KroneckerDelta[j,5]-KroneckerDelta[j,2],{j,1,5}];
Minimize[Flatten[{Diss,(Subscript[C, 25])}],{(Subscript[V, 1]),(Subscript[V, 2]),(Subscript[V, 3]),(Subscript[V, 4]),(Subscript[V, 5])}]

to precisely the same result.

To obtain all possible effective resistance values one would—if using the variational method—have to repeatedly adjust the constraint equations and re-calculate. But the Klein-Randić method supplies them all at once:

Table[(Subscript[R, effective])[i,j],{i,1,5},{j,1,5}]//MatrixForm

Conclusion

Klein-Randić works when the resistances are arbitrary. But for its magical efficiency one does pay a price: the method has—in contrast to the variational method—nothing to say about the values of the nodal potentials or branch currents. It is remarkable that it manages to address intrinsic properties of the circuit—properties that the circuit possess whether or not or how the circuit is connected to a power source—without drawing upon such information.